//给你一个长度为 n 下标从 0 开始的整数数组 maxHeights 。 
//
// 你的任务是在坐标轴上建 n 座塔。第 i 座塔的下标为 i ，高度为 heights[i] 。 
//
// 如果以下条件满足，我们称这些塔是 美丽 的： 
//
// 
// 1 <= heights[i] <= maxHeights[i] 
// heights 是一个 山脉 数组。 
// 
//
// 如果存在下标 i 满足以下条件，那么我们称数组 heights 是一个 山脉 数组： 
//
// 
// 对于所有 0 < j <= i ，都有 heights[j - 1] <= heights[j] 
// 对于所有 i <= k < n - 1 ，都有 heights[k + 1] <= heights[k] 
// 
//
// 请你返回满足 美丽塔 要求的方案中，高度和的最大值 。 
//
// 
//
// 示例 1： 
//
// 
//输入：maxHeights = [5,3,4,1,1]
//输出：13
//解释：和最大的美丽塔方案为 heights = [5,3,3,1,1] ，这是一个美丽塔方案，因为：
//- 1 <= heights[i] <= maxHeights[i]  
//- heights 是个山脉数组，峰值在 i = 0 处。
//13 是所有美丽塔方案中的最大高度和。 
//
// 示例 2： 
//
// 
//输入：maxHeights = [6,5,3,9,2,7]
//输出：22
//解释： 和最大的美丽塔方案为 heights = [3,3,3,9,2,2] ，这是一个美丽塔方案，因为：
//- 1 <= heights[i] <= maxHeights[i]
//- heights 是个山脉数组，峰值在 i = 3 处。
//22 是所有美丽塔方案中的最大高度和。 
//
// 示例 3： 
//
// 
//输入：maxHeights = [3,2,5,5,2,3]
//输出：18
//解释：和最大的美丽塔方案为 heights = [2,2,5,5,2,2] ，这是一个美丽塔方案，因为：
//- 1 <= heights[i] <= maxHeights[i]
//- heights 是个山脉数组，最大值在 i = 2 处。
//注意，在这个方案中，i = 3 也是一个峰值。
//18 是所有美丽塔方案中的最大高度和。
// 
//
// 
//
// 提示： 
//
// 
// 1 <= n == maxHeights <= 10³ 
// 1 <= maxHeights[i] <= 10⁹ 
// 
//
// Related Topics 栈 数组 单调栈 👍 12 👎 0


package LeetCode.editor.cn;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.List;

/**
 * @author ldltd
 * @date 2023-12-23 23:20:18
 * @description 2865.美丽塔 I
 */
public class BeautifulTowersI{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 Solution solution = new BeautifulTowersI().new Solution();
			solution.maximumSumOfHeights(Arrays.asList(1000000000,1000000000,1000000000));
	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
		//暴力枚举
	public long maximumSumOfHeights1(List<Integer> maxHeights) {
		long res=0;
		int size = maxHeights.size();
		for (int i = 0; i < size; i++) {
			long t=maxHeights.get(i);
			long sum=t;
			for (int j = i-1; j >=0; j--) {
				t=Math.min(t,maxHeights.get(j));
				sum+=t;
			}
			t=maxHeights.get(i);
			for (int j = i+1; j < size; j++) {
				t=Math.min(t,maxHeights.get(j));
				sum+=t;
			}
			res=Math.max(res,sum);
		}
		return res;
	}
		 //单调栈，计算0-i左侧递增，元素和最大是多少，i-n-1递减，元素和最大
	//则左右和为结果
    public long maximumSumOfHeights(List<Integer> maxHeights) {
		long res=0;
		int size = maxHeights.size();
		Deque<Integer> stack=new ArrayDeque<>();
		stack.push(size);
		long sum=0;
		long [] suf=new long[size+1];
		for (int i = size-1; i >=0; i--) {
			long t=maxHeights.get(i);
			while (stack.size()>1&&t<=maxHeights.get(stack.peek())){
				int j = stack.pop();
				//比如  1 2 777，此时栈只存了一个7，index是n-3,则sum应该减去((n-1)-(n-3))*7
				sum-= (long) maxHeights.get(j) *(stack.peek()-j);
			}
			//然后加上
			sum+=(long) t*(stack.peek()-i);
			suf[i]=sum;
			stack.push(i);
		}
		stack.clear();
		sum=0;
		stack.push(-1);

		long pree=0;
		for (int i = 0; i < size; i++) {
			int t=maxHeights.get(i);
			while (stack.size()>1&&t<=maxHeights.get(stack.peek())){
				int j=stack.pop();
				pree-=(long) maxHeights.get(j)*(j-stack.peek());
			}
			pree+=(long) t*(i-stack.peek());
			res=Math.max(res,pree+suf[i+1]);
			stack.push(i);
		}
		return res;

		/*
		可以不用另一個數組直接得出答案
		long [] pre=new long[size+1];
		for (int i = 0; i <size; i++) {
			int t=maxHeights.get(i);
			while (stack.size()>1&&t<=maxHeights.get(stack.peek())){
				int j = stack.pop();
				//比如  1 2 777，此时栈只存了一个7，index是n-3,则sum应该减去((n-1)-(n-3))*7
				sum-= (long) maxHeights.get(j) *(j-stack.peek());
			}
			//然后加上
			sum+= (long) t *(i-stack.peek());
			pre[i]=sum;
			stack.push(i);
		}


		for (int i = 0; i < size; i++) {
			res=Math.max(pre[i]+suf[i+1],res);
		}
		return res;*/
	}
}
//leetcode submit region end(Prohibit modification and deletion)

}
